package com.shuang.tree34;

public class ConstructMaximumBinaryTree {

    //递归处理 前序 中左右 在原数组上进行操作 每次将数组索引传进递归函数 左闭右开原则
    public TreeNode constructMaximumBinaryTree(int[] nums) {

        TreeNode root =  constructMaximumBinaryTree1(nums, 0, nums.length);
        return root;
    }

    public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex){

        //终止条件
        //没有元素
        if (rightIndex - leftIndex < 1){
            return null;
        }
        // 找到叶子节点返回节点
        if (rightIndex - leftIndex == 1){
            return new TreeNode(nums[leftIndex]);
        }

        //找数组中最大元素的值作为中节点 并将索引找到 用于切割数组
        int maxValue = nums[leftIndex];
        int maxValueIndex = leftIndex;

        for (int i = leftIndex + 1; i < rightIndex; i++){
            if (nums[i] > maxValue){
                maxValue = nums[i];
                maxValueIndex = i;
            }
        }

        //中节点
        TreeNode root = new TreeNode(maxValue);

        //左
        root.left = constructMaximumBinaryTree1(nums, leftIndex, maxValueIndex);

        //右
        root.right = constructMaximumBinaryTree1(nums, maxValueIndex + 1, rightIndex);

        return root;
    }
}
